#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

string karatsubaMul(string, string, int);
string schoolAdd(string, string, int);

string karatsubaMul(string str_1, string str_2, int Dec) {
	/*
		* 使用karatsuba算法实现乘法
		* str_1 : string
		* str_2 : string
		* Dec	: int
		* return : string
	*/
	char result[1024] = { 0 };
	char c[1024] = { 0 };
	int str_1_len = str_1.size();
	int str_2_len = str_2.size();

	reverse(str_1.begin(), str_1.end());
	reverse(str_2.begin(), str_2.end());

	for (int i = 0; i < str_2_len; ++i) {
		for (int j = 0; j < str_1_len; ++j) {
			int k = i + j;
			c[k] += (str_1[j] - '0') * (str_2[i] - '0');
			if (c[k] > (Dec - 1)) {
				c[k + 1] += (c[k] / Dec);
				c[k] = c[k] % Dec;
			}
		}
	}

	int j;
	for (j = str_1_len + str_2_len; j > 0; --j) {
		if (c[j] != 0) {
			break;
		}
	}
	int pos = 0;
	for (int i = j; i >= 0; --i) {
		result[pos++] = c[i] + '0';
	}

	string result_str(result);

	return result_str;
}


string schoolAdd(string str_1, string str_2, int Dec) {
	/*
		* 使用算术运算算法实现加法
		* str_1 : string
		* str_2 : string
		* int	: int
		* return : string
	*/
	char a[1024] = { 0 }, b[1024] = { 0 }, result[1024] = { 0 };

	//  一个为m位的数与一个为n位的数相加的数的位数最大不可超过max(m, n) + 1 
	int N = (str_1.length() > str_2.length() ? str_1.length() : str_2.length()) + 1;

	//  倒序存储便于计算 
	for (int i = str_1.length() - 1, j = 0; i >= 0; i--, j++)
		a[j] = str_1[i];

	for (int i = str_2.length() - 1, j = 0; i >= 0; i--, j++)
		b[j] = str_2[i];

	for (int i = 0, c = 0; i < N; i++) {
		//  相加后的余数
		result[i] = ((a[i] - '0') + (b[i] - '0') + c) % Dec + '0';
		//  相加后的进位 
		c = ((a[i] - '0') + (b[i] - '0') + c) / Dec;
	}

	//  检查最后一位是否为0，如果是则不输出 
	if (result[N - 1] == '0') {

		string result_str(result);

		result_str = result_str.substr(0, N - 1);

		reverse(result_str.begin(), result_str.end());

		return result_str;
	}
	else {

		string result_str(result);

		result_str = result_str.substr(0, N);

		reverse(result_str.begin(), result_str.end());

		return result_str;
	}
}


int main() {

	string I_1 = "", I_2 = "";

	int B = 10;

	cout << "Please enter: I1, I2, B in sequence" << endl;

	cin >> I_1 >> I_2 >> B;

	string add = schoolAdd(I_1, I_2, B);

	string mul = karatsubaMul(I_1, I_2, B);

	cout << add << " " << mul << endl;

	return 0;
}
